% Define document
\documentclass[11pt]{scrartcl}

% Import packages
\usepackage[dutch,english]{babel}
\usepackage{graphicx}
\usepackage{caption}
\usepackage{listings}
\usepackage{parskip} % split paragraphs by vertical space
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{gensymb}
\usepackage{tabularx} % for multicolumns
\usepackage{polynom} % long devision

\usepackage{tikz} 
\usetikzlibrary{calc,intersections,through,backgrounds}


% Begin document
\begin{document}
\selectlanguage{dutch}


%Add title
\title{Oefeningen TAI: \\
Oefenzitting 5: Factoriseren en Lineaire Blockcodes}
\date{}
\maketitle



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% About
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{About}
Uitwerking van oefenziting 5 van Toepassingen van Algebra in Informatica gedoceerd in de 3e Bachelor Informatica aan de KULeuven in 2012.

Latex code van dit document te vinden op:\\
SVN checkout: \texttt{https://oefenzittingen-tai.googlecode.com/svn/trunk/}\\
Google code: \texttt{https://code.google.com/p/oefenzittingen-tai/}

Credits: Peter Roelants
%TODO: put your name here

Te gebruiken op eigen risico!




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 1 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 1}

Ontbind $x^n -1$ in irreduceerbare factoren over $GF(q)$ voor:

(a) $(n,q) = (15, 4)$

(b) $(n,q) = (5, 4)$

(c) $(n,q) = (15, 3)$



\subsection*{1: extra info}
Factoriseren $x^n -1$ over $GF(q)$: p.28.



\subsection*{oplossing 1.(a)}
$(n,q) = (15, 4)$\\
$n = 4^2 -1 = 16 - 1 = 15$ ($\Rightarrow$ werkwijze p.28 gebruiken)

1. Construeer het uitbreidingsveld $GF(4^2)$ van $GF(4)$:\\ 
Zie oefenzitting 4: 3.b

2. Neem een primitief element $\alpha \in GF(4^2)$:\\
$\alpha \in GF(4^2)$: Zie oefenzitting 4: 3.b

3. Bepaal de cyclotomische nevenklassen modulo $15 = 4^2 -1$ over $GF(4)$:\\
Zie oefenzitting 4: 4.d

4. Bepaal voor elke nevenklasse de minimaalveelterm:\\
Zie oefenzitting 4: 3.d

5. Het product van alle minimaalveeltermen is gelijk aan $x^{15} - 1$:\\
$x^{15} - 1 = (x + 1)(x^2 + \xi x + \xi)(x^2 + \xi x + x + \xi + 1)(x^2 + \xi x + 1)(x + \xi)(x^2 + \xi x + x + 1)(x^2 + x + \xi)(x + \xi + 1)(x^2 + x + \xi + 1)$



\subsection*{oplossing 1.(b)}
$(n,q) = (5, 4) \Rightarrow (x^5 -1)$ factoriseren over $GF(4)$.

$5 \neq 4^k - 1 \Rightarrow$ we kunnen de procedure op p.28 niet gebruiken.

$\Rightarrow$ gebruik procedure op p.30.\\
Kies $k$:
\begin{itemize}
  \item $k = 1$\\
  $4^1 \pmod 5 = 4 \neq 1$
  \item $k = 2$\\
  $4^2 \pmod 5 = 16 \pmod 5 = 1$\\
  $\Rightarrow 4^2 -1 \pmod 5 = 0$\\
  $4^2 - 1 = 15$, is veelvoud van 5.\\
  $4^2 - 1 = 15 = n * l = 5 * 3 \Rightarrow l = 3$
\end{itemize}
$\Rightarrow$ kies $k = 2$ met $l = 3$, $n = 5$ en $q = 4$.

Primitief element $GF(4^2) = \alpha$ met $\alpha$ nulpunt van $x^2 + \xi x + \xi$ (zie oefenzitting 4, oef 3.b).\\
$\Rightarrow \beta = \alpha^{(4^{2}-1)/5} = \alpha^{l} = \alpha^{3}$

Bepaal de elementen: (zie oefenzitting 4, oef 3.c)\\
$\beta^0 = (\alpha^3)^0 = \alpha^0 = 1$\\
$\beta^1 = (\alpha^3)^1 = \alpha^3 = \alpha + \xi + 1$\\
$\beta^2 = (\alpha^3)^2 = \alpha^6 = \alpha \xi$\\
$\beta^3 = (\alpha^3)^3 = \alpha^9 = \alpha \xi + \xi + 1$\\
$\beta^4 = (\alpha^3)^4 = \alpha^{12} = \alpha + 1$\\
$\beta^5 = (\alpha^3)^5 = \alpha^{15} = 1$

Bepaal de cyclotomische nevenklassen en minimaalveeltermen: (zie oefenzitting 4, oef 3.d)\\
\begin{itemize}
  \item $\alpha$:\\
  $C_{\alpha,0} = \{ 0 \} \rightarrow m^{(0)}  = (x - \alpha^0) = x + 1$\\
  $C_{\alpha,3} = \{ 3, 12 \} \rightarrow m^{(3)} = (x - \alpha^3)(x - \alpha^{12}) = x^2 + \xi x + 1$\\
  $C_{\alpha,6} = \{ 6, 9 \} \rightarrow m^{(6)} = (x - \alpha^6)(x - \alpha^{9}) = x^2 + \xi x + x + 1$

  \item $\beta$:\\
  $C_{\beta,0} = \{ 0 \}$ (komt overeen met $C_{\alpha,0}$)\\
  $C_{\beta,1} = \{ 1,4 \}$ (komt overeen met $C_{\alpha,3}$)\\
  $C_{\beta,2} = \{ 2,3 \}$ (komt overeen met $C_{\alpha,6}$)
\end{itemize}

$\Rightarrow (x^5 - 1) =$\\
$(x - \beta^0)((x - \beta^1)(x - \beta^4))((x - \beta^2)(x - \beta^3)) =$\\
$(x - \alpha^{0})((x - \alpha^{3})(x - \alpha^{12}))((x - \alpha^{6})(x - \alpha^{9})) =$\\
$(m^{(0)}) (m^{(3)}) (m^{(6)}) =$\\
$(x + 1) (x^2 + \xi x + 1) (x^2 + \xi x + x + 1)$



\subsection*{oplossing 1.(c)}
$(n,q) = (15, 3) \Rightarrow (x^{15} - 1)$ ontbinden over $GF(3)$.

$GF(3)$ is een veld met karakteristiek 3. (Karakteristiek: p. 10)\\
$GF(3)$ is een eindig veld $\Rightarrow$ $|GF(3)| = p^k = 3^1$. (Gevolg 3, p.11, ook eigenschap Galoisveld).\\
$\Rightarrow$ gebruik maken stelling 22, p.20 (Freshman's dream).\\
$\Rightarrow x^{15} - 1 = (x^5)^3 - 1^3 = (x^5 - 1)^3$

Verder $x^5 - 1$ verder ontbinden over $GF(3)$:\\
$x^5 - 1 = (x + 2) (x^4 + x^3 + x^2 + x + 1)$

$\Rightarrow x^{15} - 1 = ((x + 2)(x^4 + x^3 + x^2 + x + 1))^3$\\
$= (x + 2)^3 (x^4 + x^3 + x^2 + x + 1)^3$ (stelling 22, p.20)

% TODO: meer info?





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 2}
Bepaal de graad van alle irreduceerbare factoren van $x^{17} - 1$ over $GF(2)$.


\subsection*{oplossing 2}
Het is voldoende om de cyclotomische nevenklassen modulo 17 over $GF(2)$ te bepalen.\\
$C_{0} = \{ 0 \} \rightarrow$ minimaalveelterm graad = 1\\
$C_{1} = \{ 1,2,4,8,16,15,13,9 \} \rightarrow$ minimaalveelterm graad = 8\\
$C_{2} = \{ 3,6,12,7,14,11,5,10 \} \rightarrow$ minimaalveelterm graad = 8

Factorisatie $x^{17} - 1$ over $GF(2)$ = $(1 + x) (1 + x^3 + x^4 + x^5 + x^8) (1 + x + x^2 + x^4 + x^6 + x^7 + x^8)$ (via WolframAlpha).

%TODO: meer info






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Oef 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Opgave 3}
Gegeven een $(n,k)$ lineaire blokcode $\mathbb{C}$ over $GF(2)$:\\
$\mathbb{C} = \{ 
000000,
000111,
011001,
011110,
101011,
101100,
110010,
110101
 \}$
 
(a) Is deze code wel een blokcode?

(b) Is deze code wel lineair?

(c) Wat is $n$? Wat is $k$?

(d) Construeer een generatormatrix $G$ voor deze code. Codeer enkele informatiewoorden.

(e) Ga over op een equivalente code met een generatormatrix $\tilde{G}$ in standaardvorm.

(f) Bepaal de pariteitsmatrix $\tilde{H}$ van die equivalente code.

(g) Bepaal de pariteitsmatrix $H$ van de oorspronkelijke code.

(h) Hoeveel fouten kan men detecteren? Hoeveel fouten kan men verbeteren?

(i) Vervolledig de decoderingstabel voor deze code?
%tabel
\begin{table}[h!]
\centering
\begin{tabular}{ c | c c c c c c c }
	000000 &	000111 &	011001 &	011110 &	101011 &	101100 &	110010 &	110101 \\
	\hline
	100000 &	100111 &	111001 &	111110 &	001011 &	001100 &	010010 &	010101 \\
	010000 &	010111 &	001001 &	001110 &	111011 &	111100 &	100010 &	100101 \\
	001000 &	001111 &	010001 &	010110 &	100011 &	100100 &	111010 &	111101 \\
	000100 &	000011 &	011101 &	011010 &	101111 &	101000 &	110110 &	110001 \\
	000010 &	000101 &	011011 &	011100 &	101001 &	101110 &	110000 &	110111
\end{tabular}
\end{table}

(j) Bepaal de syndroomtabel voor deze code.

(k) Je ontvangt 110011. Wat is de gedecodeerde boodschap?

(l) Is deze code perfect?



\subsection*{oplossing 3.(a)}
Alle woorden van een blokcode moeten dezelfde lengte $n$ hebben. (p.33 cursus)\\
$n = 6 \Rightarrow$ OK, code is een blokcode.



\subsection*{oplossing 3.(b)}
De som en verschil van twee codewoorden moet ook een codewoord zijn. (p.39 cursus)\\
som van 2 codewoorden $\in \mathbb{C} \Rightarrow$ OK.


\subsection*{oplossing 3.(c)}
$n$ is de lengte van het codewoord: $n = 6$\\
$k$ is de lengte van het informatiewoord: $k = 3$\\
$k$ is ook de grootte van de basis = $\{ 000111, 011001, 101011 \}$ (p.40)


\subsection*{oplossing 3.(d)}
Generatormatrix: p.40 cursus.

basis = $\{ 000111, 011001, 101011 \} \Rightarrow$\\
$ G = 
\begin{bmatrix}
	0	&	0	&	0	&	1	&	1	&	1 \\
   	0	&	1	&	1	& 	0	&	0	&	1 \\
   	1	&	0	&	1	&	0	&	1	&	1
\end{bmatrix}
$ 

Coderen informatiewoorden, vb:\\
%i1
$i_1 = 100$\\
$\Rightarrow c_1 = i_1 * G = 
\begin{bmatrix}
	1 & 0 & 0
\end{bmatrix}
*
\begin{bmatrix}
	0	&	0	&	0	&	1	&	1	&	1 \\
   	0	&	1	&	1	& 	0	&	0	&	1 \\
   	1	&	0	&	1	&	0	&	1	&	1
\end{bmatrix}
=
\begin{bmatrix}
	0	&	0	&	0	&	1	&	1	&	1 
\end{bmatrix}
$

%i2
$i_2 = 101$\\
$\Rightarrow c_2 = i_2 * G = 
\begin{bmatrix}
	1 & 0 & 1
\end{bmatrix}
*
\begin{bmatrix}
	0	&	0	&	0	&	1	&	1	&	1 \\
   	0	&	1	&	1	& 	0	&	0	&	1 \\
   	1	&	0	&	1	&	0	&	1	&	1
\end{bmatrix}
=
\begin{bmatrix}
	1	&	0	&	1	&	1	&	0	&	0 
\end{bmatrix}
$



\subsection*{oplossing 3.(e)}
Systematische code: p.43 cursus.

$ G = 
\begin{bmatrix}
	0	&	0	&	0	&	1	&	1	&	1 \\
   	0	&	1	&	1	& 	0	&	0	&	1 \\
   	1	&	0	&	1	&	0	&	1	&	1
\end{bmatrix}
$ $\rightarrow$ rij 1 en 4 wisselen, dan rij 4 en 3 wisselen $\rightarrow$\\
$ \tilde{G} = 
\left[
\begin{array}{c c c | c c c}
	1	&	0	&	0	&	0	&	1	&	1 \\
   	0	&	1	&	0	& 	1	&	0	&	1 \\
   	0	&	0	&	1	&	1	&	1	&	1
\end{array}
\right]
= 
\left[
\begin{array}{c | c}
	I & P
\end{array}
\right]
$

rij-permutaties: $123456 \rightarrow 423156 \rightarrow 421356$



\subsection*{oplossing 3.(f)}
Pariteitsmatrix: p.40 cursus.\\
Constructie $\tilde{H}$: p.43 cursus.

$\tilde{H} = 
\left[
\begin{array}{c | c}
	-P^T & I
\end{array}
\right]
$

$ \tilde{G} = 
\left[
\begin{array}{c c c | c c c}
	1	&	0	&	0	&	0	&	1	&	1 \\
   	0	&	1	&	0	& 	1	&	0	&	1 \\
   	0	&	0	&	1	&	1	&	1	&	1
\end{array}
\right]
= 
\left[
\begin{array}{c | c}
	I & P
\end{array}
\right]
\Rightarrow$\\
% P matrix
$
P = 
\left[
\begin{array}{c c c}
		0	&	1	&	1 \\
   	 	1	&	0	&	1 \\
   		1	&	1	&	1
\end{array}
\right]
$
$
\Rightarrow
-P = 
\left[
\begin{array}{c c c}
		0	&	-1	&	-1 \\
   	 	-1	&	0	&	-1 \\
   		-1	&	-1	&	-1
\end{array}
\right] \pmod{2}
= 
\left[
\begin{array}{c c c}
		0	&	1	&	1 \\
   	 	1	&	0	&	1 \\
   		1	&	1	&	1
\end{array}
\right]
\Rightarrow
$\\
% -P Transpose matrix
$
-P^T = 
\left[
\begin{array}{c c c}
		0	&	1	&	1 \\
   	 	1	&	0	&	1 \\
   		1	&	1	&	1
\end{array}
\right]
\Rightarrow
$\\
% H tilde matrix
$
\tilde{H} = 
\left[
\begin{array}{c c c | c c c}
	0	&	1	&	1	&	1	&	0	&	0 \\
   	1	&	0	&	1	& 	0	&	1	&	0 \\
   	1	&	1	&	1	&	0	&	0	&	1
\end{array}
\right]
$



\subsection*{oplossing 3.(g)}
$H$ bepalen door de omgekeerde permutatie van $G$ naar $\tilde{G}$ toe te passen op $\tilde{H}$.

$ \tilde{H} = 
\left[
\begin{array}{c c c | c c c}
	0	&	1	&	1	&	1	&	0	&	0 \\
   	1	&	0	&	1	& 	0	&	1	&	0 \\
   	1	&	1	&	1	&	0	&	0	&	1
\end{array}
\right]
$ $\rightarrow$ rij 4 en 3 wisselen, dan rij 1 en 4 wisselen $\rightarrow$\\
$ H = 
\left[
\begin{array}{c c c c c c}
	1	&	1	&	1	&	0	&	0	&	0 \\
   	1	&	0	&	0	& 	1	&	1	&	0 \\
   	1	&	1	&	0	&	1	&	0	&	1
\end{array}
\right]
$

rij-permutaties: $123456 \rightarrow 124356 \rightarrow 324156$




\subsection*{oplossing 3.(h)}
Foutendetectie: p. 36 cursus.\\
Foutencorrectie: p. 37 cursus.

afstand = $d = min\ dt(c_1,c_2)\ met\ c_1,c_2 \in \mathbb{C} = 3$

$\Rightarrow$ aantal fouten detecteren = $s = d - 1 = 3 - 1 = 2$

$\Rightarrow$ aantal fouten verbeteren = $t = (d-1)/2 = (3-1)/2 = 1$



\subsection*{oplossing 3.(i)}
Decoderingstabel: p.44 cursus.\\*
Elk element van $GF(q)^n$ moet er exact \'e\'en keer in voorkomen. In dit geval zijn dat er $2^6$. Het aantal rijen in deze tabel is $q^n/q^k$.

%tabel
\begin{table}[h!]
\centering
\begin{tabular}{ c | c c c c c c c c }
	000000 &	000111 &	011001 &	011110 &	101011 &	101100 &	110010 &	110101 & ($\leftarrow$ codewoorden) \\
	\hline
	100000 &	100111 &	111001 &	111110 &	001011 &	001100 &	010010 &	010101 & \\
	010000 &	010111 &	001001 &	001110 &	111011 &	111100 &	100010 &	100101 & \\
	001000 &	001111 &	010001 &	010110 &	100011 &	100100 &	111010 &	111101 & \\
	000100 &	000011 &	011101 &	011010 &	101111 &	101000 &	110110 &	110001 & \\
	000010 &	000101 &	011011 &	011100 &	101001 &	101110 &	110000 &	110111 & \\
	000001 &	000110 &	011000 &	011111 &	101010 &	101101 &	110011 &	110100 & \\
	100001 &	100110 &	111000 &	111111 &	001010 &	001101 &	010011 &	010100 & 
\end{tabular}
\end{table}



\subsection*{oplossing 3.(j)}
Syndroomtabel: p.46 cursus.

%tabel
\begin{table}[h!]
\centering
\begin{tabular}{ c | c  }
	vertegenwoordiger & syndroom \\
	\hline
	000000 &	000 \\
	100000 &	111 \\
	010000 &	101 \\
	001000 &	100 \\
	000100 &	011 \\
	000010 &	010 \\
	000001 &	001 \\
	100001 &	110 
\end{tabular}
\end{table}


\subsection*{oplossing 3.(k)}
Ontvangen van $v = 110011$.

$\Rightarrow$ syndroom $s = v H^T = 
\begin{bmatrix}
	1 & 1 & 0 & 0 & 1 & 1
\end{bmatrix}
*
\begin{bmatrix}
	1 & 1 & 1 \\
	1 & 0 & 1 \\
	1 & 0 & 0 \\
	0 & 1 & 1 \\
	0 & 1 & 0 \\
	0 & 0 & 1
\end{bmatrix}
=
\begin{bmatrix}
	0 & 0 & 1
\end{bmatrix}
$

$\Rightarrow$ via syndroomtabel: $e = [000001]$

$\Rightarrow$ verzonden codewoord = 
$v - e = [000001] - [110011] = [110010]$



\subsection*{oplossing 3.(l)}
Perfecte codes: p.49 cursus.

pakkingsstraal: $r_p = 1$\\
dekkingsstraal: $r_d = 2$

$\Rightarrow$ code is niet perfect want $r_p \neq  r_d$.

$\Rightarrow$ code is quasi-perfect want $r_d =  r_p + 1$.



\end{document}
